This invention pertains to multi-nodal communication network organization, and more particularly to unique procedures whereby a network, having initially no defined central controller, or coordinator, (CCo) can self-organize in a way which involves nodal discovery, followed by organization which leads to (a) selection, ultimately, of the most suited node to be the CCo, (b) selection of the optimal collection of nodes to define the active network, (c) definition of network topology in terms of both non-hidden (NHN) and hidden (HN) nodes, and (d) the effective establishment of satisfactory connectivity between all of the active network nodes, including the establishment of intermediary proxy nodes which act as surrogates for the determined CCo to facilitate communication between HNs and the CCo. Connections between nodes for communication take place through a suitable medium, or channel, which may be either wired or wireless.
In the description herein of the present invention, the term “topology” is used. Topology relates to knowledge regarding (a) the identities of all nodes in a network, (b) the states of connectivity between nodes, (c) the identity of the eventually selected CCo, (d) the identities of so-called hidden nodes (defined below), and (e) the identity of what is referred to herein (later explained) as a proxy node.
In self-organizing ad-hoc communication networks which are, or are to be, centrally controlled, nodes need to learn about the presence of other nodes (devices) in the network, as well as about the availability of acceptable bi-directional links between any two nodes (topology discovery process). The nodes must be able to organize themselves into networks controlled by a suitable, selected Central Coordinator (CCo). This is required (a) any time a node joins or leaves the network, (b) during recovery from network or node failure, (c) when the network is initialized, and (d) when any event that changes the topology of the network occurs (i.e., CCo shuts down, better CCo is available in the network, link characteristics change, etc.). The process of network organization requires a protocol—and effective methodology—for the exchange of relevant information between devices (nodes), and for decision-making processes required to organize the network. As used herein, the term “network” refers to a collection of nodes which effectively can all “hear” one another. Side headings and lead-in topic phrases presented and featured in the text which now follows identify various activities, algorithmic characteristics and communication messages which collectively describe this invention.
The present invention, in its preferred and best mode form, proposes unique Centralized Network Organization and Topology Discovery Algorithms (CNOA). These algorithms address the following matters:
1. Device Network Entry (SCAN and ASSOCIATE): Such procedures are required to describe how a device may join a network that has already been established. The impact of a new device joining the network must also be addressed by these procedures.
2. Discovery of Network Topology: This is a process by which nodes learn of each other's presence, of device capabilities, and of the qualities of communications links between them. At the end of this process, the CCo has a global knowledge of the network link characteristics, and proceeds to build a global connectivity database called the TOPOLOGY TABLE.
3. Establishment of an ad-hoc Network (identification of all nodes that belong to the “network”: The “network” is defined as a logical association of nodes that can all communicate with one another. The CCo needs to determine this collection of nodes.
4. Identification of a Central Coordinator (CCo): This function determines which device in the network is most suited to fulfill the role of CCo for the network.
5. Identification of Hidden Nodes (HN): This function identifies those nodes called “hidden nodes”, which cannot communicate directly with the CCo, but may be able to communicate with other nodes in the network.
6. Identification of Proxy Coordinators (PCos) to service “hidden nodes”: This function allows the CCo to identify nodes that can perform the function of PCos. PCos act as CCo surrogates, and allow the CCo to communicate with HNs. These PCo nodes are also referred to herein as proxy nodes.
CNOA Assumes the Following Attributes:
1. A CCo is always present in the network. If one is not present, the first node to join the network declares itself to be the CCo.
2. The CCo controls access to the medium (channel) by designating a time frame, and, utilizing any appropriate approach, by scheduling access for each node within each time frame as required by the node. Each time frame is delineated by the transmission of a BEACON_MSG message.
3. There exists at least one interval in each time frame (or one in several time frames) dedicated to contention access where communication-medium access is based on a contention-based algorithm, such as Slotted ALOHA. Any node may use this interval to communicate with the CCo, or with a proxy node.
Certain unique aspects of CNOA include:
1. An approach whereby the CCo schedules bandwidth allocations to be used by individual nodes for the transmission of discover messages. Other nodes listen to transmissions, and generate individual connectivity lists which are relayed back to the CCo. The CCo then generates a global connectivity graph for the network, called a TOPOLOGY TABLE.
This approach is unique in many ways. Usually, ad-hoc networks do not maintain global network connectivity information. The present invention enables the efficient generation and collection of network-wide connectivity information. Every node learns of its connectivity with all other nodes in one step. Nodes do not have to “probe” individual links on an ad-hoc basis as some prior art approaches require. Further, CNOA enables the identification of HNs, and allows these HNs to communicate with the CCo via intermediary nodes called, as mentioned earlier, proxy nodes. Practice of the invention makes it possible for HNs automatically to identify suitable proxy nodes with which to communicate. This then, allows HNs to join the network. It also uniquely allows HNs to participate in a discovery process for the whole network. No known prior art approach for ad-hoc networks provides these capabilities.
2. A methodology that identifies the optimal CCo; a methodology that identifies the optimal collection of nodes to constitute a network; a methodology that identifies HNs; and a methodology that identifies optimal PCos to connect HNs to the CCo and the network.
As will be seen, the present invention features a series of analyses that a CCo can perform on a TOPOLOGY TABLE which is generated at the end of the DISCOVERY process to accomplish all the above-listed functions. There is no known precedent in the prior art that allows a CCo optimally to select a node to fulfill the role of CCo, and to perform all of the other mentioned functions, in this manner. This approach of the invention is extremely efficient. It results in an optimal network configuration (i.e., best CCo device, best PCos, best network and hidden node configuration). Such an optimal configuration is determined with the least overhead in terms of message exchanges between nodes and CCo. It is also efficient in that the optimal configuration is generated and maintained in a minimal amount of time, or delay, incurred.
The CNOA algorithm describes the following functions: initial network establishment when no network exists, processes for devices joining and leaving the network, devices discovering or learning the topology of the network, identification of “hidden nodes”, identification of proxy controllers to service hidden nodes, and selection of an optimal Central Coordinator from among all devices in the network. This algorithm defines procedures that enable hidden nodes to join the network. Topology discovery is the process by which individual nodes in a network (e.g., hosts, bridges, routers, etc.) learn the configuration of the network and the connectivity between any two individual nodes. This is important for network management, and for efficient routing and resource management. In the case of ad-hoc networks, the processes of discovery and network organization (how nodes organize themselves into clusters or sub-nets with designated subnet managers or controllers) are fundamental to the efficient operation of such networks.
Thus, and further explaining preliminarily, the present invention uniquely addresses topology, discovery and network organization, and other concomitant, issues and problems in an ad-hoc network with the following characteristics:
1. All nodes in a “network” share a common transmission medium (in both frequency and time domain). This medium may be wired or wireless. Multiple node access is provided. Nodes are not required to possess any “carrier sense” capability.
2. Connectivity between any two nodes is a function of the capabilities of such nodes, and of channel characteristics. Under the best transmission conditions for digital communications (power, modulation density, symbol duration, coding, etc.), all nodes do not necessarily hear all other nodes. Further, links between devices are not symmetric i.e., node A may hear (receive and correctly decode packets) from another node B, while B may not hear A.
3. The network in its operational mode, configured by practice of the present invention, consists of host nodes, a designated controller for the network called the Central Coordinator (CCo), and where appropriate, a set of Proxy Coordinators (PCo) to communicate with nodes that cannot directly communicate (in one link) with the CCo, or with other nodes in the network.
4. The network is self-organizing, in that the nodes have to establish the configuration of the network, and to choose a CCo. Such decision-making may be accomplished in a distributed fashion by each node making an independent decision, or by a central repository of relevant information. Network organization is required during initial network establishment, recovery from failures of hosts, PCos, CCos, when channel conditions between nodes change significantly causing outages, and when new nodes join or leave the network.
5. Once a network has been organized, the determined CCo controls the transmission activity of the nodes in the network. The existence of a CCo in the network implies:
(a) A timing reference which is available, allowing nodes in the network to synchronize to a universal time frame during which access is scheduled.
(b) Access to the medium/channel is scheduled by the CCo. Nodes are allowed to transmit only upon receiving explicit authorization either from the CCo or from a PCo. The CCo may also schedule time within a time frame for random access of the channel, during which all nodes are free to transmit as per the random access protocol agreed to by all nodes.
6. Nodes can directly communicate with one another, during time periods scheduled by the CCo, and do not have to use the CCo as an interim node or relay.
These and various other features and advantages which are offered by the present invention will become more fully apparent as the detailed description provided now below is read in conjunction with the illustrative drawings.